package quwei;

import java.util.Scanner;

public class Test4_4 {

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.println("输入字符串str1：");
        String str1=scanner.next();
        System.out.println("输入字符串str2：");
        String str2=scanner.next();
        int answer=editDistance(str1,str2);                  //求编辑距离
        System.out.println(str1+"和"+str2+"的编辑距离是："+answer);
    }

    public static int editDistance(String str1,String str2) {
        int len1=str1.length();                              //计算字符串的长度
        int len2=str2.length();
        int[][] d=new int[len1+1][len2+1];                   //d[i][j]表示str1前i个字符和str2前j个字符的编辑距离

        for(int i=0;i<=len1;i++)                             //当第二个字符串长度为0时，编辑距离初始化为i
            d[i][0]=i;
        for(int j=0;j<=len2;j++)                             //当第一个字符串长度为0时，编辑距离初始化为j
            d[0][j]=j;

        for(int i=1;i<d.length;i++) {                        //遍历str1的每个字符
            for(int j=1;j<d[i].length;j++) {                 //与第二个字符串的每个字符进行比较
                int diff;                                    //判断str1[i]是否等于str2[j]，相等为0
                if(str1.charAt(i-1)==str2.charAt(j-1)) {     //字符串小标从0开始
                    diff=0;
                }
                else
                    diff=1;

                int temp=Math.min(d[i-1][j]+1, d[i][j-1]+1);  //去三者中最小值
                d[i][j]=Math.min(temp,d[i-1][j-1]+diff);
            }
        }
        return d[len1][len2];
    }

}
